//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
//
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 1036 👎 0


package leetcode.editor.cn;

class 数组中的逆序对 {
    public static void main(String[] args) {
        Solution solution = new 数组中的逆序对().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] nums, tmp;

        public int reversePairs(int[] nums) {
            this.nums = nums;
            tmp = new int[nums.length];
            return merge_sort(0,nums.length-1);
        }

        private int merge_sort(int left, int right) {
            if (left >= right) return 0;
            int mid = left + ((right - left) >> 1);
            int res = merge_sort(left, mid) + merge_sort(mid + 1, right);

            for (int i = left; i <= right; i++) {
                tmp[i] = nums[i];
            }
            
            int l = left, r = mid + 1;
            for (int i = left; i <= right; i++) {
                if (l > mid) nums[i] = tmp[r++];
                else if (r > right || tmp[r] >= tmp[l]) nums[i] = tmp[l++];
                else {
                    nums[i] = tmp[r++];
                    res += mid - l + 1;
                }
            }
            
            return res;
        }


        /**
         * 暴力不通过
         *
         * @param nums
         * @return
         */
        public int reversePairs1(int[] nums) {
            int counts = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] > nums[j]) counts++;
                }
            }
            return counts;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
